package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * 将单向链表按某值划分成左边小、中间相等、右边大的形式
 */
public class Code16_listPartition {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(8, 4, 2, 7, 1, 5, 10, 3, 5, 2);
        int pivot = 5;
        ListNode listNode = listPartition(head, pivot);
        ListNodeUtils.print(listNode);
    }

    public static ListNode listPartition(ListNode head, int pivot) {
        ListNode sH = null;
        ListNode sT = null;
        ListNode eH = null;
        ListNode eT = null;
        ListNode mH = null;
        ListNode mT = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            //确保每个节点在被处理后不再指向原链表中的其他节点，这样链表的连接不会形成环。即每个节点一旦处理完，就不会再和原链表的其他节点产生连接。
            head.next = null;
            if (head.val < pivot) {
                if (sH == null) {
                    sH = head;
                    sT = head;
                } else {
                    sT.next = head;
                    sT = head;
                }
            } else if (head.val == pivot) {
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                if (mH == null) {
                    mH = head;
                    mT = head;
                } else {
                    mT.next = head;
                    mT = head;
                }
            }
            head = next;
        }
        if (sT != null) { // 小于区域
            sT.next = eH;
            eT = eT == null ? sT : eT;
        }
        if (eT != null) {
            eT.next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mH);
    }
}
